Cite this Article
Chen Dong-Xu, Liu Rui-Feng, Zhang Pei, Wang Yun-Long, Li Hong-Rong, Gao Hong, Li Fu-Li. Realization of quantum permutation algorithm in high dimensional Hilbert space. Chinese Physics B, 2017, 26(6): 060305  
Permissions
Realization of quantum permutation algorithm in high dimensional Hilbert space
Chen Dong-Xu1, Liu Rui-Feng1, Zhang Pei1, 2, †, Wang Yun-Long1, Li Hong-Rong1, Gao Hong1, Li Fu-Li1
Key Laboratory of Quantum Information and Quantum Optoelectronic Devices, School of Science, Xi’an Jiaotong University, Xi’an 710049, China
Key Laboratory of Quantum Information, University of Science and Technology of China, Hefei 230026, China

 

† Corresponding author. E-mail: zhangpei@mail.ustc.edu.cn

Abstract

Quantum algorithms provide a more efficient way to solve computational tasks than classical algorithms. We experimentally realize quantum permutation algorithm using light’s orbital angular momentum degree of freedom. By exploiting the spatial mode of photons, our scheme provides a more elegant way to understand the principle of quantum permutation algorithm and shows that the high dimension characteristic of light’s orbital angular momentum may be useful in quantum algorithms. Our scheme can be extended to higher dimension by introducing more spatial modes and it paves the way to trace the source of quantum speedup.

PACS: 03.67.Ac;03.67.-a;42.50.-p
Keyword:quantum permutation algorithm;orbital angular momentum;Fourier transformation
1. Introduction

Since the concept of quantum computer was proposed by Richard Feynman,[1] a lot of work has been done to realize quantum computation. It has been demonstrated that quantum computation can reduce the computational complexity in comparison to its classical counterpart. Quantum algorithms[2]are the basis to realize quantum computation. With more and more effort made to design quantum algorithms, quantum computation based on well-designed algorithms has shown great advantage over classical computation. Deutsch’s algorithm[3–5] is the first quantum algorithm proposed to prove the speedup. Shor’s factoring algorithm[6,7] which is shown to be able to break the safety of the RSA encryption algorithm has been realized to factor 15.[7] Other algorithms such as Grover’s searching algorithm,[8–10] quantum simulation algorithm,[11,12] quantum algorithm for solving linear equations,[13–15] and quantum annealing algorithm[16,17] have also been proven to be advantageous in reducing the space complexity and the time complexity compared with classical algorithms.

Much effort has been made to understand the sources of acceleration of quantum computation. Mark Howard et al.[18] argued that quantum contextuality supplies the source of quantum speedup. A quantum permutation algorithm is proposed by Gedik et al.[19] to demonstrate that quantum entanglement is not necessary in quantum speedup. The algorithm deals with the similar black box issue with Deutsch’s algorithm. It shows the speedup in deciding the type of the black box. Gedik’s algorithm has been realized in NMR systems by using three-level system[20] and four-level system[19] and also in linear optical systems[21,22] by using hybrid Hilbert space[22] and entangled states.[21] Qubit is the building unit of a quantum computer and it poses no entanglement. Construction of a quantum computer requires integration of multiple qubits. It is the entanglement between qubits that completes the computing task. On the other hand, a single degree of freedom (DoF) whose dimension is higher than two can also be used to realize quantum computation without entanglement involved. In this article, we realize Gedik’s algorithm with a single qudit utilizing light’s orbital angular momentum (OAM) DoF. Our scheme can be extended to higher dimensional system because of the high dimension characteristic of OAM DoF which shows the potential of light’s OAM in high dimension quantum computation and provides a way to realize quantum computing without entanglement in high dimension system.

2. Quantum permutation algorithm

Quantum permutation algorithm is proposed to solve tasks involve cyclic transformations in d-dimensional system. Consider a black box which maps d input states into d output states. There are two possible subsets of the output states, clockwise and anticlockwise. The order of the input states doesn’t change in the clockwise subset except a shift of the states. In the anticlockwise subset, however, the order of input changes in addition to a shift of the states. The mapping of the black box can be formalized as follows:

where , determines clockwise permutation () and anticlockwise permutation (). For example, maps to , while maps to . We can write down the eight different mappings using Cauchy’s two-line notation when d=4

Classically, we need at least two measurements to determine whether the permutation is positive or negative. Gedik et al.[19] showed that using quantum algorithm, only one measurement is needed to solve the problem which is twice faster than classic algorithm. Figure 1 shows the quantum circuit of Gedik’s permutation algorithm. In Gedik’s algorithm, the input state encounters Quantum Fourier Transformation (QFT)[23] before entering the black box, the black box performs some mapping operation on the transformed state, an inverse QFT is carried out after the black box and the final state is measured.

Fig. 1. (color online) Quantum circuit model of Gedik’s permutation algorithm. A QFT is carried out before the input state enters the black box which performs the 2d different operations. Following an inverse QFT, the final state is measured.

In Gedik’s permutation algorithm, initial state is prepared. After QFT, the quantum state is transformed into

which turns into superposition of with equal weight. As we can see from Eq. (2), in the positive cases, the effect of the permutation operation is a shift of the states in . The relative phases of form an arithmetic progression thus the shift of the states result in an overall phase of

After an inverse QFT, is transformed back to with an overall phase

In the negative cases, the permutation transforms to (by we mean mod(), the same as below)

by replacing with K, we can obtain

In a similar way, an inverse QFT transforms into with an overall phase

The orthogonality of the final states (Eq. (6) and Eq. (9)) brings the possibility of identifying the parity of the operation with a single measurement in quantum manner. For example, in the case of d = 4, can be chosen to be or , which results to be or , respectively, under negative permutation operation, and results to be themselves under positive permutation operation. In the next section, we present a proof-of-principle experiment to demonstrate the speedup in identifying the parity of the permutation using light’s OAM DoF in a more elegant way compared with NMR system and other linear optical systems.

3. Experimental realization

It is shown that electromagnetic fields with vortex phase (, ϕ is the azimuthal angle) pose OAM among which Laguerre–Gaussian (LG) beam is a common type. The OAM of photons has been extensively studied and applied in quantum information fields.[24–29] We integrate the QFT step in Fig. 1 into the preparation of the initial state by directly generating . Besides, the inverse QFT and the measurement of the final state is replaced by distinguishing the output state from the black box (see text for details). In the following we first introduce our experiment and extend our scheme to higher dimensional systems.

3.1. Quantum permutation in a single qudit

In our experiment, the qudit is a subspace of the infinite dimensional Hilbert space of light’s OAM.[30] We choose the optical mode to be LG modes which are solutions of paraxial wave equation

where is the Rayleigh range, w(0) is the beam waist. is an associated Laguerre polynomial. The subspace is chosen to be which corresponds tothe logical states , respectively.

Figure 2(a) shows our experimental setup. Light emits from He–Ne laser with wavelength of 633 nm. After being collimated, the beam impinges on a digital micromirror device (DMD)[24] on which a hologram used to produce is displayed. The hologram is filled with vales 0 and 1. The DMD works as an amplitude-type spatial light modulator which consists of two-dimensional micromirror arrays. The mirrors reflect light to 12° or −12° direction depending on the values of the bits. A 4f system consists of and is used to select the first order of the diffracted light. The black box is to perform the eight different mapping operations. The output state is measured by a charge coupled device (CCD) camera.

Fig. 2. (color online) (a): Schematic diagram of the proposed experiment, collimated light beam impinges on DMD which is loaded with the hologram pattern to produce the Fourier transformed states of the initial states, .The beam reflects in +12° direction is blocked. A 4f system selects the 1st diffraction order. The produced statespass through the black box which performs the permutation operations. A CCD camera records the patterns. (b): Details of the OAM sorter. (c)–(j): Details of the eight possible operations.

The eight different mapping operations correspond to the different cyclic transformations of OAM states among , and . To realize such transformations, we make use of an OAM sorter[31,32] along with spiral phase plates (SPP) as is indicated in Figs. 2(c)–2(j).[33] The details of the OAM sorter are shown in Fig. 2(b). Photons with even OAMs interfere constructively in port A while those with odd OAMs interfere constructively in port B. The OAM sorters in our experiment works as an even–odd OAM sorter. Figures 2(c)–2(f) are the mapping operations. Figure 2(c) is identity operation corresponding to . In Fig. 2(d) the SPP first adds to the OAM which transforms to . The OAM sorter reflects photons with odd OAMs and transmits photons with even OAMs. We insert a Dove lens in the upper arm of the Mach–Zehnder interferometer to change the sign of the even OAMs, the final state is transformed to which corresponds to operation. In Fig. 2(e), we add to the even OAMs which transforms the OAM space to then reverse the sign of OAM to which corresponds to operation. In Fig. 2(f), we first reverse the sigh of odd OAMs then add to the beam to transform the OAM space to then reverse the sign of OAM to which corresponds to operation. Figures 2(g)–2(j) are the mapping operations. In Fig. 2(g), we reverse the sign of odd OAMs to transforms the OAM space to which corresponds to operation. In Fig. 2(h), we add to the even OAMs. For odd OAMs, we first reverse the sign of OAMs then add then reverse the sign. These operationstransform the OAM space to which corresponds to operation. In Fig. 2(i), we add to the even OAMs then reverse the sign of them. The OAM space is tranformed to which corresponds to operation. In Fig. 2(j), we simply add to the beam then reverse the sign of OAMs which transforms the OAM space to which corresponds to operation. The lenses in the operations are used to image the optical field of the back focal plane of f2 onto the surface of the SPPs and the Dove lenses are used to compensate the reflection of photons. To realize the transformations accurately, the optical path differences (ϕ1 represents the optical path of the upper path and ϕ2 represents the optical path of the down path) of the two paths which overlap on the beam splitter (BS) in Figs. 2(d)–2(i) must be corrected, which is realized by adjusting piezoceramics (PZT, not shown in the figures). The optical path differences and the topological charges of the SPPs of the eight operations are summarized in Table 1. While calculating , the effects of mirror, 4f systems and dove prism (oriented at 0°) are taken into consideration as they have an extra π phase on odd OAMs compared with the effects on even OAMs. Note that our experiment realizes permutation algorithm with half possibility but it is easily to improve to one by cascading another interferometer.

Table 1.

The topological charges of the SPP added to the photons and the optical path differences of the two paths in the second interferometer.

.

As is indicated by Eq. (6) and Eq. (9), in the case of d = 4, if the input logical state is or the output state will change. In our experiment, we test OAM state and in correspondence whose Fourier transformations are and , respectively. Note that and have completely different spatial modes, see Figs. 3(a1)–3(a2). A simple bracket leads us to .

Fig. 3. (color online)Experimental results. Panels (a1) and (a2) are the simulations of and , respectively. Panels (a3) and (a4) are the output of under and operations, respectively. We can learn the parity of the permutation by observing the difference between Panels (a3) and (a4). Panel (b) shows the fidelities of the the final states under the four operations in which cases the states are unchanged, the fidelities tend to identity. Panel (c) shows the fidelities of the the final state under the four operations in which case the states are changed to their quadrature states, the fidelities tend to zero.

According to Eq. (6) and Eq. (9), to decide the parity of the operation, we need to distinguish whether the output pattern is or . In order to judge the output pattern, we fit the output pattern with fitting function , in doing so, we treat the weight of the computational basis being equal and the relative phases of and , and being π. The fidelity is calculated and the results are shown in Fig. 3. Figure 3(b) shows the fidelities of the output state under operations and figure 3(c) shows the fidelities of the output state under operations. We can see that the fidelities of positive operations tend to identity while the fidelities of negative operations tend to zero, which implies the invariability of the states in positive operations and the alternation of the states in negative operations.

The utility of light’s OAM brings us another method to test our result. The difference between the output states corresponds to the differencebetween the output spatial modes. For example, figure 3(a3) is the output of under operation and figure 3(a4) is the output of under operation. We can see that figure 3(a3) is similarwith figure 3(a1) () while figure 3(a4) is similar with figure 3(a2) (). By directly observing the pattern, we can learn that figure 3(a3) corresponds to positive operation while figure 3(a4) corresponds to negative operation, which is much simpler than any previously reportedmethod.[19–22]

3.2. Quantum permutation in higher-dimensional systems

The OAM of photons forms an infinite dimensional Hilbert space. By making use of this characteristic, our scheme can be extended to higher dimensional system by introducing more OAM states. For example, we can test the permutation algorithm when d = 5. In this case, the subspace can be chosen to be . Figure 4 is an example of implementing operation. In Fig. 4, SPP1 adds to the input state . The OAM beam splitters (OAMBS) consist of a Mach–Zehnder interferometer with Dove lens in both arms. OAMBS1 works as an even–odd sorter which reflects odd OAMs and transmits even OAMs (with the sign reversed). OAMBS2 reflects and transmits and . OAMBS3 reflects and transmits . The two dove lenses are used to compensate the sign of the OAM states. SPP2 adds to . The optical paths of the interferometers should also be corrected. Under such operation, is mapped to .

Fig. 4. (color online) Extension of our scheme to realize when d = 5.

The OAM DoF can be coupled with other DoFs of photons, polarization, path, etc. We can also couple OAM with other DoFs to realize permutation algorithm in high dimensional space. For example, coupling polarization DoF and OAM DoF can be used to test the algorithm in dimensional system. One of the possible operations can be found in Ref. [34].

4. Conclusion

In conclusion, we propose an experimental realization of quantum permutation algorithm based on light’s OAM which theoretically forms an infinite Hilbert space. By ultilizing the cyclic transformations of the OAM states, we performed the eight possible permutation operations in four-dimensional subspace of light’s OAM. While performing the experiment, the phase differences of the interferometers should be carefully calculated and adjusted. The stability of the interferometers should also be high enough during the whold experiment. We integrate the QFT of OAM states into the generation of the initial states to simplify the experiment and we analysize the final states by numerical fitting because QFT of OAM states is still difficult to be implemented. Our experiment demonstrates Gedik’s algorithm in an elegant way. Unlike other linear optical schemes[21,22] which use two qubit or two DoFs of photon, our scheme realize quantum speedup with a single DoF of photons with no entanglement involved. The experimental results show that the black box issue can be solved within a single measurement in quantum manner which is twice faster than classical algorithm. Our experiment can be extend to higher quantum permutation with a single DoF of a photon and provides a possible way to explore the origin of quantum speedup.

Reference
[1] Feynman R P 1982 Int. J. Theor. Phys. 21 467
[2] Montanaro A 2016 npj Quantum Information 2 15023
[3] Deutsch D 1985 Proc. R. Soc. Lond. 400 97
[4] Jozsa R Deutsch D 1994 Proc. R. Soc. A 439 553
[5] Zhang P Liu R F Huang Y F Gao H Li F L 2012 Phys. Rev. 82 064302
[6] Shor P W 1994 IEEE Comp. Soc. 11 124
[7] Martin-Lopez E Laing A Lawson T Alvarez R Zhou X Q O’Brien J L 2012 Nat. Photon. 6 773
[8] Grover L K 1997 Phys. Rev. Lett. 79 325
[9] Li T Bao W Lin W Zhang H Fu X 2014 Chin. Phys. Lett. 31 050301
[10] Zhang Y Bao W Wang X Fu X 2015 Chin. Phys. 24 110309
[11] Lloyd S 1996 Science 273 1073
[12] Buluta I Nori F 2009 Science 326 108
[13] Harrow A W Hassidim A Lloyd S 2009 Phys. Rev. Lett. 103 150502
[14] Cai X D Weedbrook C Su Z E Chen M C Gu M Zhu M J Li L Liu N L Lu C Y Pan J W 2013 Phys. Rev. Lett. 110 230501
[15] Pan J Cao Y Yao X Li Z Ju C Chen H Peng X Kais S Du J 2014 Phys. Rev. 89 022313
[16] Bian Z Chudak F Israel R Lackey B Macready W G Roy A 2016 arXiv: 1603.03111%20[quan-ph]
[17] Amin M 2015 Phys. Rev. 92 052323
[18] Howard M Wallman J Veitch V Emerson J 2014 Nature 510 351
[19] Gedik Z Silva I A Çakmak B Karpat G Gé Vidoto E L Soares-Pinto D O deAzevedo E R Fanchini F F 2015 Sci. Rep. 5 14671
[20] Dogra S Arvind Dorai K 2014 Phys. Lett. 378 3452
[21] Zhan X Li J Qin H Bian Z Xue P 2015 Opt. Express 23 18422
[22] Wang F Wang Y Liu R Chen D Zhang P Gao H Li F 2015 Sci. Rep. 5 10995
[23] Nielsen M A Chuang I L 2000 Quantum computation and quantum information Cambridge Cambridge University Press 10.1017/CBO9780511976667
[24] Mirhosseini M Mangna-Loaiza O S Chen C Rodenburg B Malik M Boyd R W 2013 Opt. Express 21 30196
[25] Nagali E Sciarrino F De Martini F Marrucci L Piccirillo B Karimi E Santamato E 2009 Phys. Rev. Lett. 103 013601
[26] Mair A Vaziri A Weihs G Zeilinger A 2001 Nature 412 313
[27] Xu Y Huang Y Hu L Zhang P Wei D Li H Gao H Li F 2013 Chin. Phys. Lett. 30 100304
[28] Liu R Zhang P Gao H Li F 2012 Chin. Phys. Lett. 29 124203
[29] Wang L Zhao S Gong L Cheng W 2015 Chin. Phys. 24 120307
[30] Allen L Beijersbergen M W Spreeuw R J C Woerdman J P 1992 Phys. Rev. 45 8185
[31] Leach J Padgett M J Barnett S M Franke-Arnold S Courtial J 2002 Phys. Rev. Lett. 88 257901
[32] Fu D Jia J Zhou Y Chen D Gao H Li F Zhang P 2015 Acta Phys. Sin. 64 130704
[33] Schlederer F Krenn M Fickler R Malik M Zeilinger A 2016 New J. Phys. 18 043019
[34] Krenn M Malik M Fickler R Lapkiewicz R Zeilinger A 2016 Phys. Rev. Lett. 116 090405